"""
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示：
0 <= nums.length <= 105
-109<= nums[i]<= 109
nums是一个非递减数组
-109<= target<= 109
链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
"""


class Solution:
    def search(self, nums, target: int):
        def helper(target):
            i, j = 0, len(nums) - 1
            # 这边是“小于等于”，因此当循环结束后，ij不重合，且如果存在target值的话，
            # i的位置就是右边界（target值序列右边第一个大于target值的位置），
            # 因为最后一次循环一定是i=mid+1；且此时j指向target
            while i <= j:
                mid = (i + j) // 2
                # 这里是“小于等于”，目的是为了确定右边界，就是说当mid等于target时，
                # 因为不确定后面还有没有target，所以同样需要左边收缩范围
                if nums[mid] <= target:
                    i = mid + 1
                else:
                    j = mid - 1
            return i

        a = helper(target)
        b = helper(target - 1)
        return a - b


class Solution1:
    def search(self, nums, target: int):
        def helper(tar):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= tar:
                    left = mid + 1
                else:
                    right = mid - 1
            return left

        a = helper(target)
        b = helper(target - 1)
        return a - b


class Solution2:
    def search(self, nums, target: int) -> int:
        """
        这个做法是定好红蓝边界，判断函数为isBlue(),
        即isBlue()返回为真代表左边的都是蓝色区域
        最后的返回值left为左边界最右边，
        right为右边界最左边
        """

        def isBlue(a, b):
            if a <= b:
                return True
            else:
                return False

        def helper(tar):
            n = len(nums)
            left, right = -1, n

            while left + 1 != right:
                mid = (left + right) // 2
                if nums[left] <= tar:
                    left = mid
                else:
                    right = mid

            return left

        a = helper(target)
        b = helper(target - 1)
        return a - b


class Solution3:
    def search(self, nums, target: int):
        def helper(target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left

        def helper1(target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left
        a = helper(target)
        print(target, a)

        b = helper1(target)
        print(target - 1, b)
        return a - b




if __name__ == "__main__":
    """
    """
    A = Solution()
    nums = [7, 7, 7, 7, 7, 7]
    target = 7
    print(A.search(nums, target))

    A = Solution3()
    nums = [6, 7, 7, 7, 7, 7]
    target = 7
    print(A.search(nums, target))
